The present invention relates to fast packet switching and particularly to self-routing packet switching in a communication system.
In a communication system, the ability to transmit many diverse forms of information (such as voice, video, image, graphics, text, computer data, control data, electronic funds and electronic mail) in an integrated manner, has long been needed. Information to be transferred through a system is conveniently classified into two categories. Real time signals such as voice and video represent one class that presents a reasonably constant traffic load to the system. This class tolerates relatively high losses and error rates within the system, but this class is not tolerant of delays and delay variances. Data signals such as computer data and electronic funds represent a class that presents a rapidly fluctuating traffic load to the system. Although this class is intolerant of errors, this class can tolerate long and variable delays. Due to the different characteristics of these two classes of traffic, two different methods of switching have developed, namely circuit switching for real time signals and packet switching for data signals.
Although many attempts have been made to integrate circuit and packet switching, further improvements are still needed for a commercially successful integrated communications system. Some such improvements are described in the above cross-referenced applications.
In the cross-referenced applications, self-routing switching elements are employed to form a high-capacity, fast-packet switch having the capability of handling both voice and data traffic by virtue of the use of small packets in combination with virtual circuits across the system.
In the cross-referenced applications, the self-routing switching elements include a plurality of selectors each having an input for incoming tagged packet signals; a plurality of arbiters each having an output for transmitted packet signals, and a signal path connection between each selector and each arbiter; each selector being operable to examine the tag of an incoming packet signal and route the packet signal to the arbiter identified by the examined tag, and each arbiter being operable to select one of the packet signals received from any of the selectors and transmit that packet signal to its output, at the same time acting on other selectors to prevent the transmission of subsequent packet signals until the transmission of the selected packet signal is complete.
The input port controllers, the output port controllers, and the switch fabric each work independently, without any requirement for central control, upon the packets which arrive at their inputs. In general, each input port controller can be fed from a queue of incoming packets in an input buffer and each output port controller can feed an output buffer. The structure of the switch fabric is a multi-stage interconnection system constructed from a number of identical switching elements connected in stages. The throughput of the structure is increased by connecting multiple planes in parallel to offer multiple paths between each input/output pair of controllers.
In the basic operation of the switch, the input port controller provides a packet tag to the head of each input packet. This tag indicates the desired destination of the packet and may consist, for example, of the binary representation of the destination output port number. The value of the tag may be derived from virtual circuit connection information within each packet. The interconnection system is arranged so that to forward an input packet towards the desired destination, a switching element selects the digit(s) within the tag, corresponding to the current stage within the system, and forwards the packet over the corresponding output. The switching elements may contain internal buffers, to form a buffered system, or may not, to form a non-buffered system. Buffered systems offer greater throughput per switching element but voice packet priority is more difficult than in a non-buffered system.
In the cross-referenced applications, each connection consists of a forward path carrying packets forward and a reverse path which carries a reverse signal back towards the input controller. The input controller first operates to launch a packet into the switch fabric. If the destination port is busy, or if no free path through the switch fabric is available, the switch fabric in one embodiment returns a busy signal shortly after the input port controller has launched the last bit of the tag into the switch fabric. On receiving a busy signal, the input controller abandons the attempted transmission of the packet, removes the attempt from the switch fabric and waits for a short period (typically equivalent to about 10 percent of the duration of a packet). After this period the input controller makes another attempt at transmitting the packet, and so on, until transmission is successful. A packet transmission is assumed to be successful if no busy signal is received by the end of transmission of the packet.
The throughput of the switch fabric of the cross-referenced applications is enhanced by the use of large size switching elements and by the use of multiple paths through the switch fabric between every input/output controller pair using a mechanism for locating a free path to the destination from the set of all equivalent paths.
While the cross-referenced applications are substantial improvements in providing fully integrated packet switches, still additional improvements are needed.